B14 - Another Subset Sum - 競プロ

B14 - Another Subset Sum

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cm

提出

code: python

n, k = map(int, input().split())

a = list(map(int, input().split()))

# O(pow(2, 30))

a.sort()

# print(a)

# 1, 2, 5, 7, 9, 18

asum = 0

for v in a:

asum.append(asum-1 + v)

# print(asum)

# 0, 1, 3, 8, 15, 24, 42

# どう分割するか O(N)

# 何個選ぶか O(pow(2, N))

解答

code: python

import bisect

import itertools

n, k = map(int, input().split())

a = list(map(int, input().split()))

sum1 = []

for v in itertools.product(0, 1, repeat=len(l1)):

sum = 0

for i, w in enumerate(v):

if w:

sum += l1i

sum1.append(sum)

sum2 = []

for v in itertools.product(0, 1, repeat=len(l2)):

sum = 0

for i, w in enumerate(v):

if w:

sum += l2i

sum2.append(sum)

sum1.sort()

sum2.sort()

# 二分探索で sum1i + sum2j = k となるものが存在するかを見つける

for i in range(len(sum1)):

pos = bisect.bisect_left(sum2, k-sum1i)

if pos < len(sum2) and sum2pos == k-sum1i:

print("Yes")

exit(0)

print("No")